<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <title>Unix Family Tree</title>
    <style>
        @import url(../style.css);
    .background {
        stroke: white;
        stroke-width: 1px;
        fill: white;
    }

    .node {
        stroke: black;
        stroke-width: 1.5px;
        cursor: move;
        fill: lightcoral;
    }

    .link {
        fill: none;
        stroke: #000;
        stroke-width: 3px;
        opacity: 0.7;
        marker-end: url(#end-arrow);
    }

    .label {
        fill: black;
        font-family: Verdana;
        font-size: 25px;
        text-anchor: middle;
        cursor: move;
    }
    </style >
    </head >
<body >
    <a href="../index.html">cola.js home</a>
    <h1>Unix Family Tree</h1>
    <h2>Directed graph flow layout and shortest-path edge routing</h2>
    <script src="../extern/graphlib-dot.min.js"> </script>
    <script src="../extern/d3v4.js"></script>
    <script src="../cola.min.js"></script>
    <link rel="stylesheet" href="../extern/hljs/styles/github.css">
    <script src="../extern/hljs/highlight.pack.js"></script>
    <script>
        hljs.initHighlightingOnLoad();
        var d3cola = cola.d3adaptor(d3).convergenceThreshold(0.1);

        var width = 960, height = 700;

        var outer = d3.select("body").append("svg")
            .attr('width',width)
            .attr('height',height)
            .attr('pointer-events',"all");

        outer.append('rect')
            .attr('class','background')
            .attr('width',"100%")
            .attr('height',"100%")
            .call(d3.zoom().on("zoom", redraw));

        var vis = outer
            .append('g')
            .attr('transform', 'translate(250,250) scale(0.3)');

        function redraw() {
            vis.attr("transform", d3.event.transform);
        }

        outer.append('svg:defs').append('svg:marker')
            .attr('id','end-arrow')
            .attr('viewBox','0 -5 10 10')
            .attr('refX',8)
            .attr('markerWidth',6)
            .attr('markerHeight',6)
            .attr('orient','auto')
          .append('svg:path')
            .attr('d','M0,-5L10,0L0,5L2,0')
            .attr('stroke-width','0px')
            .attr('fill','#000');

        d3.text("graphdata/unix.dot", function (f) {
            var digraph = graphlibDot.parse(f);

            var nodeNames = digraph.nodes();
            var nodes = new Array(nodeNames.length);
            nodeNames.forEach(function (name, i) {
                var v = nodes[i] = digraph._nodes[nodeNames[i]];
                v.id = i;
                v.name = name;
            });

            var edges = [];
            for (var e in digraph._edges) {
                var edge = digraph._edges[e];
                edges.push({ source: digraph._nodes[edge.u].id, target: digraph._nodes[edge.v].id });
            }

            d3cola
                .avoidOverlaps(true)
                .convergenceThreshold(1e-3)
                .flowLayout('x', 150)
                .size([width, height])
                .nodes(nodes)
                .links(edges)
                .jaccardLinkLengths(150);

            var link = vis.selectAll(".link")
                .data(edges)
                .enter().append("path")
                .attr("class", "link");

            var margin = 10, pad = 12;
            var node = vis.selectAll(".node")
                .data(nodes)
                .enter().append("rect")
                .classed("node", true)
                .attr('rx',5)
                .attr('ry',5)
                .call(d3cola.drag);

            var label = vis.selectAll(".label")
                .data(nodes)
                .enter().append("text")
                .attr("class", "label")
                .text(function (d) { return d.name; })
                .call(d3cola.drag)
                .each(function (d) {
                    var b = this.getBBox();
                    var extra = 2 * margin + 2 * pad;
                    d.width = b.width + extra;
                    d.height = b.height + extra;
                });

            var lineFunction = d3.line()
                .x(function (d) { return d.x; })
                .y(function (d) { return d.y; });

            var routeEdges = function () {
                d3cola.prepareEdgeRouting();
                link.attr("d", function (d) {
                    return lineFunction(d3cola.routeEdge(d
                     // show visibility graph
                        //, function (g) {
                        //    if (d.source.id === 10 && d.target.id === 11) {
                        //    g.E.forEach(function (e) {
                        //        vis.append("line").attr("x1", e.source.p.x).attr("y1", e.source.p.y)
                        //            .attr("x2", e.target.p.x).attr("y2", e.target.p.y)
                        //            .attr("stroke", "green");
                        //    });
                        //    }
                        //}
        ));
                });
                if (isIE()) link.each(function (d) { this.parentNode.insertBefore(this, this) });
            }
            d3cola.start(50, 100, 200).on("tick", function () {
                node.each(function (d) { d.innerBounds = d.bounds.inflate(-margin); })
                    .attr("x", function (d) { return d.innerBounds.x; })
                    .attr("y", function (d) { return d.innerBounds.y; })
                    .attr("width", function (d) {
                        return d.innerBounds.width();
                    })
                    .attr("height", function (d) { return d.innerBounds.height(); });

                link.attr("d", function (d) {
                    var route = cola.makeEdgeBetween(d.source.innerBounds, d.target.innerBounds, 5);
                    return lineFunction([route.sourceIntersection, route.arrowStart]);
                });
                if (isIE()) link.each(function (d) { this.parentNode.insertBefore(this, this) });

                label
                    .attr("x", function (d) { return d.x })
                    .attr("y", function (d) { return d.y + (margin + pad) / 2 });

            }).on("end", routeEdges);
        });
        function isIE() { return ((navigator.appName == 'Microsoft Internet Explorer') || ((navigator.appName == 'Netscape') && (new RegExp("Trident/.*rv:([0-9]{1,}[\.0-9]{0,})").exec(navigator.userAgent) != null))); }
    </script>
    This is a cola.js rendering of the classic graphviz dot <a href="http://www.graphviz.org/content/unix">example</a>.  We use <a href="https://github.com/cpettitt/graphlib-dot">graphlib-dot.js</a> to parse the dot file.
    The initialization for cola here is interesting:
    <pre><code>d3cola
    .avoidOverlaps(true)
    .flowLayout('x', 150)
    .size([width, height])
    .nodes(nodes)
    .links(edges)
    .jaccardLinkLengths(150);
</code></pre>
    In particular, the call to <code>flowLayout</code> causes all edges not involved in a cycle (strongly connected component) to have a separation constraint generated between their source and sink,
    with a minimum spacing set to 150.  Specifying the <code>'x'</code> axis achieves a left-to-right flow layout.  The default is top-to-bottom flow layout (i.e. <code>'y'</code>).
    You can also specify a function as the second argument to <code>flowLayout</code> that returns different separations for each edge.  Specify a different minimum as a second parameter to <code>flowLayout</code>.
    <p>
    Another feature of this example is <i>shortest-path edge routing</i>.  That is, after layout stops, the edge paths are routed to avoid passing through node boundaries.
    To do this, we call the following function on the layout "end" event:
    </p>
<pre><code>var routeEdges = function () {
    d3cola.prepareEdgeRouting(margin / 3);
    link.attr("d", function (d) { return lineFunction(d3cola.routeEdge(d)); });
    if (isIE()) link.each(function (d) { this.parentNode.insertBefore(this, this) });
}</code></pre>
    <p>
        The function <code>prepareEdgeRouting(padding)</code> creates a <i>tangent visibility graph</i> over the polygonal boundaries of the nodes.
        The <code>padding</code> parameter controls how close edges can come to the node boundaries.
        Here we set it to be a third of the minimum spacing that layout allows between nodes.
        This visibility graph looks like this:
    </p>
<img src="unixVisibilityGraph.png" width="400px"/>
<p>
    The call to <code>d3adaptor.routeEdge</code> for each edge, uses the Dijkstra algorithm to find a shortest path through the visibility graph from the
    centre of the source node to the centre of the target node.
    </p><p>
    The last bit: <code>if (isIE()) link.each(...</code> is an IE10/11 specific hack to force it to redraw the edges.  This is necessary because
    IE has trouble with SVG markers (in this case the arrow heads).
</p>
    <script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-63535113-1', 'auto');
  ga('send', 'pageview');

    </script>
</body>
</html>
